package TDAMapeo;

import TDALista.ListaSE;


/**
 * Mapeo con Hash cerrado
 * @author Jordan
 *
 * @param <K>
 * @param <V>
 */
public class HashMap<K,V> implements Map<K, V> {
	public Entrada<K, V>[] mapeo;
	
	/**
	 * Entrada para "marcar" si la posicion esta disponible o no
	 */
	public final Entrada<K, V> AVAIBLE=new Entrada<K, V>(null, null);
	
	public int size;
	
	/**
	 * factor de carga para que el mapeo quede con un mejor manejo y menor tiempo en las operaciones
	 */
	public float factorDeCarga;
	
	/**
	 * constructor por defecto, crea un arreglo de 5 entradas
	 */
	public HashMap(){
		mapeo=(Entrada<K,V>[])(new Entrada[5]);
		size=0;
		factorDeCarga=0;
	}

	/* (non-Javadoc)
	 * TERMINAR, probar de modularizar los return y los factores de carga
	 * @see Mapeo.Map#put(java.lang.Object, java.lang.Object)
	 */
	@Override
	public V put(K key, V Value) throws InvalidKeyException {
		// TODO Auto-generated method stub
		check(key);
		V res=null;
		if(factorDeCarga>0.5)
			rehash();
		int hashn=hash(key);
		Entrada<K, V> entr=new Entrada<K, V>(key, Value);
		if(mapeo[hashn]==AVAIBLE || mapeo[hashn]==null){//Si esta vacio:
			mapeo[hashn]=entr;
			size++;
			factorDeCarga= (float)size/mapeo.length;
//			return entr.getValue();
			return res; //retorno null porq es el primer elementento con el hash
		}
		if(mapeo[hashn].getKey().equals(key)){//Si ya se encuentra la clave:
			res=mapeo[hashn].getValue();
			mapeo[hashn]=entr;
			factorDeCarga= (float)size/mapeo.length;
			return res; //retorno el valor viejo
		}		
		else{//Sino:
			int i=(hashn+1)%mapeo.length;//posicion siguiente a la actual
			boolean encontre=false;
			while(i!=hashn && !encontre){//busco hasta encontrar un lugar donde poner la entrada
				if(mapeo[i]==null || mapeo[i]==AVAIBLE || mapeo[i].getKey().equals(key)){//si la posicion esta disponible:
					mapeo[i]=entr;
					encontre=true;
					size++; //puede llegar a dar mal si es q sobrescribi la entrada
					factorDeCarga= (float)size/mapeo.length;
//					return entr.getValue();//ver
					return null;
				}
				i=(i+1)%mapeo.length;
			}
		}
				
		return null;
	}
	
	private void rehash() {
		// TODO Auto-generated method stub
		Entrada<K, V>[] nuevoArreglo=new Entrada[mapeo.length*2];
		Entrada<K, V>[] aux=mapeo; //auxiliar para iterar
		mapeo=nuevoArreglo;
		factorDeCarga=0;
		size=0;
		for(Entrada<K, V> e: aux){//recorre todo el arreglo, inclusive los indices vacios
			try {
				if(e!=null)//si la entrada no es nula
					put(e.getKey(), e.getValue());
			} catch (InvalidKeyException e1) {
				e1.printStackTrace();
			}
		}
	}

	protected int hash(K key) {
		return Math.abs(key.hashCode()%mapeo.length);
	}

	private void check(K key) throws InvalidKeyException {
        if(key==null)
            throw new InvalidKeyException("llave nula!");
        
    }

	@Override
	public boolean isEmpty() {
		
		return size==0;
	}

	@Override
	public int size() {
		
		return size;
	}

	@Override
	public V get(K key) throws InvalidKeyException {
		// TODO Auto-generated method stub
		check(key);
		int hashn=hash(key);
		if(mapeo[hashn]!=null){//si es null quiere decir q no voy a encontrar la entrada con clave key
			if(mapeo[hashn].getKey().equals(key))
				return mapeo[hashn].getValue();
			else{
				int i=(hashn+1)%size;
				while(i!=hashn){
					if(mapeo[i].getKey().equals(key))
						return mapeo[i].getValue();
					i=(i+1)%size;
				}
					
			}
		}
			
		return null;
	}

	@Override
	public V remove(K key) throws InvalidKeyException {
		// TODO Auto-generated method stub
		check(key);
		int hashn=hash(key);
		if(mapeo[hashn]!=null){//si da null ese indice queire decir que no voy a poder encontrar la entrada
			if(mapeo[hashn].getKey().equals(key)){
				V res=mapeo[hashn].getValue();
				mapeo[hashn]=AVAIBLE;
				size--;
				return res;
			}
			else{
				int i=(hashn+1)%size;
				while(i!=hashn){
					if(mapeo[i].getKey().equals(key)){
						V res=mapeo[hashn].getValue();
						mapeo[hashn]=(Entrada<K, V>)AVAIBLE;
						size--;
						return res;
					}
					i=(i+1)%size;
				}
					
			}
		}
		return null;
	}

	@Override
	public Iterable<Entry<K, V>> entries() {
		ListaSE<Entry<K, V>> res=new ListaSE<Entry<K,V>>();
		for(Entrada<K, V> en: mapeo)
			if(en!=null && en!=AVAIBLE)
				res.addLast(en);
		return res;
	}

	@Override
	public Iterable<K> keys() {
		ListaSE<K> res=new ListaSE<K>();
		for(Entrada<K, V> en: mapeo)
			if(en!=null && en!=AVAIBLE)
				res.addLast(en.getKey());
		return res;
	}

	@Override
	public Iterable<V> values() {
		ListaSE<V> res=new ListaSE<V>();
		for(Entrada<K, V> en: mapeo)
			if(en!=null && en!=AVAIBLE)
				res.addLast(en.getValue());
		return res;
	}
	
	/**
	 * O(m)*O(n), m=cantidad de entradas del mapeo por parametro, n=cantidad de celdas del arreglo q recibe el mensaje
	 * @param mapeo
	 * @return
	 */
	private boolean estaContenido(Map<K, V> mapeo){
		Iterable<Entry<K, V>> entradasMapeo=mapeo.entries();//O(m)
		for(Entry<K, V> en:entradasMapeo) //O(m)
			if(!esta(en))//O(n)
				return false;
		return true;
	}

	/**
	 * O(n), n=numero de celdas del arreglo
	 * @param en
	 * @return
	 */
	private boolean esta(Entry<K, V> en) {
		int hashn=hash(en.getKey());
		int i=hashn;
		if(mapeo[hashn]==null)
			return false;
		if(mapeo[hashn].equals(en))
			return true;
		i=(i+1)%size;
		while(i!=hashn){//O(n)
			if(mapeo[i].equals(en))
				return true;
			i=(i+1)%size;
		}
					
		return false;
	}

}
